#include <bits/stdc++.h>

using namespace std;

class Solution{
public:
    bool canAliceWin(int n){
        int pick=10;
        while(n>=pick){
            n-=pick;
            pick--;
        } return (10-pick)%2;
    }
};

class Solution2{
public:
    long long shift(string s, string t, vector<int>& nextCost, vector<int>& previousCost){
        long long dis[26][26];
        for(int i=0;i<26;i++) for(int j=0;j<26;j++){
            long long x=0;
            for(int k=i;k!=j;k=(k+1)%26) x+=nextCost[k];
            long long y=0;
            for(int k=i; k!=j;k=(k+25)%26) y+=previousCost[k];
            dis[i][j]=min(x,y);
        }
        long long ans=0;
        for(int i=0;i<s.size();i++)
            ans+=dis[s[i] -'a'][t[i]-'a'];
        return ans;
    }
};

// 模拟，range, 不相交的区间
class Solution3 {
public:
    int maxRemoval(vector<int>& nums, vector<vector<int>>& queries) {
        int n=nums.size(), q=queries.size();
        sort(queries.begin(),queries.end());
        int now, ans=0;
        priority_queue<int> pq;
        int f[n+1]; memset(f,0,sizeof(f));
        for(int i=0,j=0;i<n;i++){
            now-=f[i];
            while(j<q&&queries[j][0]<=i) pq.push(queries[j][1]), j++;
            while(now<nums[i]&&!pq.empty()){
                int t=pq.top(); pq.pop();
                if(t>=i){
                    now++; ans++; f[t+1]++;
                }
            }
            if(now<nums[i]) return -1;
        }
        return q-ans;
    }
};

// 走地图， dp
class Solution4 {
public:
    int maxCollectedFruits(vector<vector<int>>& fruits) {
        int n=fruits.size();
        const long long INF=1e18;
        long long f[n][n];
        for(int i=0;i<n;i++)for(int j=0;j<n;j++) f[i][j]=-INF;

        f[0][n-1]=fruits[0][n-1];
        for(int i=1;i<n;i++)for(int j=i+1;j<n;j++){
            f[i][j]=max(f[i-1][j-1], f[i-1][j]) + fruits[i][j];
            if(j+1<n) f[i][j]=max(f[i][j],f[i-1][j-1]+fruits[i][j]);
        }

        f[n-1][0]=fruits[n-1][0];
        for(int j=1;j<n;j++) for(int i=j+1;i<n;i++){
            f[i][j]=max(f[i-1][j-1],f[i][j-1])+fruits[i][j];
            if(i+1<n) f[i][j]=max(f[i][j], f[i+1][j-1]+fruits[i][j]);
        }

        long long ans=f[n-2][n-1] + f[n-1][n-2];
        for(int i=0;i<n;i++) ans+=fruits[i][i];
        return ans;

    }
};

int main(){
    Solution s; cout<<s.canAliceWin(12)<<endl;
    vector<int> nextCost={100,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
    vector<int> preCost={1,100,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
    Solution2 s2; cout<<s2.shift("abab","baba",nextCost,preCost)<<endl;
    vector<int> nums3={2,0,2}; vector<vector<int>> queries={{0,2},{0,2},{1,1}};
    Solution3 s3; cout<<s3.maxRemoval(nums3, queries)<<endl;
    vector<vector<int>> fruits={{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};
    Solution4 s4; cout<<s4.maxCollectedFruits(fruits)<<endl;
}